LeetCode Longest Palindromic Substring 和 Manacher 算法

LeetCode Longest Palindromic Substring 题解。

题目

题目就是要求找出给定字符串的最长回文子串。

Constraints

输入是一个字符串
字符串的长度范围为0~1000
字符串中一定存在一个唯一最长回文子字符串
要求返回这个子字符串

Ideas

蛮力

从字符串的第一个字符作为回文子串的中心字符，检查这个回文子串的长度，再从第一个字符和第二个字符之间的空格作为回文子串的中心字符，检查这个回文子串的长度，依次类推，遍历完后返回最长的那个子串。

这个算法的时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。

Manacher 算法

见wikipedia

对于上面的蛮力算法，需要对回文子串的中心字符是原始字符串中的字符还是空白字符分别做处理。Manacher算法通过先对字符串做预处理使得之后不用考虑这个问题。abba变成#a#b#b#a#,这样子串的中心字符要么是#表示空白字符（这个字符可以任意只要不在原字符串中出现即可），要么就是原始字符串中的字符。

这里有一个问题，是否可以这么处理abba变成a#b#b#a,看样子是可以，但是还是会出现问题，比如这个abb变成a#b#b，在原始字符串中最长回文子串是bb，但在处理后的字符串a#b#b，以第一个b为中心字符的#b#长度为3，和以第二个#为中心的字符串b#b也为3。但是在原始字符串中，以第一个b为中心的回文子串长度为1，以第一个b和第二个b之间的空白字符为中心的回文子串bb才是长度最长的。

接下来，就可以查找出处理后的字符串的最长回文子串了。

首先需要一个数组R来保存以每一个字符作为中心字符的回文子串的半径长度。例如：

	0	1	2	3	4	5	6	7	8
s	`#`	a	`#`	b	`#`	b	`#`	a	`#`
R	0	1	0	1	4	1	0	1	0

可以发现R中的最大值就是原字符串的最长回文子串的长度。

其实这个也挺好理解的，处理后的字符串长度是原先的字符串长度的2倍加1，因为添加了length+1个#。在处理后的字符串s中，回文子串都是以s中的字符为中心的，去除了中心这个字符，回文子串的长度就是原串中回文子串长度的两倍，那么s的回文子串的半径长度就是原串中回文子串长度。

接下来就是要求这个R数组。

我们可以借助回文子串对称的特点来加快R的求解。

	0	1	2	3	4	5	6	7	8	9
s	a	a	a	b	a	b	a	a	a	b
R	0	1	0	1	4	1	0

当我们在求R[7]的时候，我们已经求出了R[0]到R[6]的值，知道R[4]等于4，即R[0..8]是回文串，R[0]和R[8]相等，R[1]和R[7]相等,R[2]和R[6]相等，R[3]和R[5]相等，由此，我们知道以s[1]为中心的回文子串在没有超出s[0..8]中的字符是和以s[7]为中心的回文子串在没有超出s[0..8]中的字符相同的。所以，R[7]至少等于Min(R[1], 4+R[4] - 7)=1。

对于超出s[0..8]范围的字符，这里就只剩下s[9]了，我们只能按照蛮力的方式来计算了。

这里我们要用maxR记录已经算出的回文子串的最右边界,用id记录这个回文子串的中心字符的下标。

这个算法的时间复杂度为$O(n)$，空间复杂度为$O(n)$。这个时间复杂度主要看maxR是如何增长的，因为处理i<maxR的情况时借助了前面已经计算出来的值，这一步为常数，而超出maxR范围的时候，每对比一次，maxR其实就增长1，当maxR为字符串长度时，之后的计算都只是使用之前已经计算的值而已。

Code

public String longestPalindrome(String s) {

        if (s == null || s.length() == 0 || s.length() == 1) return s;

        // 添加#符号
        // 这里应该有一个候选的符号列表，从该符号列表选取符号
        // 先检测字符串s是否包含该符号，如果包含就重新选一个，不包含才进行添加
        StringBuilder sb = new StringBuilder(s.length() * 2 + 1);
        sb.append('#');
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append('#');
        }

        String origin = s;
        s = sb.toString();

        int[] R = new int[s.length()];
        int id = 0;
        int maxR = 0;

        for (int i = 0; i < s.length(); i++) {
            if (i < maxR) {
                // 2 * id - i是i关于id的对称点
                // 因为题目里有说s的length最大为1000
                // 所以这里 2 * id是安全的
                R[i] = Math.min(R[2 * id - i], maxR - i);
            } 
            //else {
              //  R[i] = 0; // 默认也是0
            //}

            while (i - R[i] >= 0 && i + R[i] < s.length() && s.charAt(i - R[i]) == s.charAt(i + R[i])) {
                R[i]++;
            }
            R[i]--; // 减去s[i-0] == s[i+0]时加的

            if (i + R[i] > maxR) {
                maxR = i + R[i];
                id = i;
            }
        }

        id = 0;
        for (int i = 0; i < R.length; i++) {
            if (R[i] > R[id]) {
                id = i;
            }
        }
        // 慢一些 36ms
        //return s.substring(id - R[id], id + R[id]).replaceAll("#", "");

        // 计算出在原始字符串的位置 快一些 18ms
        int start = 0;
        int end = 0;
        if (s.charAt(mid) == '#') {
            start = mid / 2 - max / 2;
            end = mid / 2 + max / 2;
        } else {
            start = (mid - 1) / 2 - (max - 1) / 2;
            end = (mid - 1) / 2 + (max + 1) / 2;
        }
        return origin.substring(start, end);
    }

Test

LeetCode测试通过